/*
 * @lc app=leetcode.cn id=513 lang=cpp
 *
 * [513] 找树左下角的值
 *
 * https://leetcode.cn/problems/find-bottom-left-tree-value/description/
 *
 * algorithms
 * Medium (73.28%)
 * Likes:    560
 * Dislikes: 0
 * Total Accepted:    224.9K
 * Total Submissions: 306.9K
 * Testcase Example:  '[2,1,3]'
 *
 * 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
 * 
 * 假设二叉树中至少有一个节点。
 * 
 * 
 * 
 * 示例 1:
 * 
 * 
 * 
 * 
 * 输入: root = [2,1,3]
 * 输出: 1
 * 
 * 
 * 示例 2:
 * 
 * ⁠
 * 
 * 
 * 输入: [1,2,3,4,null,5,6,null,null,7]
 * 输出: 7
 * 
 * 
 * 
 * 
 * 提示:
 * 
 * 
 * 二叉树的节点个数的范围是 [1,10^4]
 * -2^31  
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    //记录最大深度 和 结果
    int MaxDepth;
    int Result;

public:
    //104. 最大深度
    void Traversal (TreeNode* node, int depth) {
        if (node == nullptr)
            return;

        //叶子节点, 由于是左优先遍历, 第一次遍历到深度最大的一定是最左下角的
        if (node->left == nullptr && node->right == nullptr) {
            if (depth <= MaxDepth)
                return;

            MaxDepth = depth;
            Result = node->val;
            return;
        }

        Traversal(node->left, depth + 1);
        Traversal(node->right, depth + 1);
    }

    int findBottomLeftValue(TreeNode* root) {
        //1. 使用层序遍历, 比较简单, 就不实现了

        //2. 使用递归
        //左下角点, 只要是左优先遍历即可, 不用在意本节点是 左 / 右 节点
        Traversal(root, 1);
        return Result;
    }
};
// @lc code=end

